「洛谷P4212/BZOJ3632」外太空旅行

发表于 | 分类于 | | 浏览量： 次

啥？NPC问题？模拟退火！！！

传送门

洛谷P4212

BZOJ3632

题解

题目很明确就是要你求一个最大团。

但是最大团问题是一个NPC问题。

所以直接上模拟退火！

先随机生成一个长度为$n$的排列，然后从前往后遍历，如果枚举到的点可以加入到当前的图中就加入。每次检验的复杂度为$O(n^2)$。每次退火的时候就随机交换排列的两个位置即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=505;const double delta=0.995;
int n,m,P[maxn],ans;bool E[maxn][maxn];
inline int Calc()
{
	static bool vis[maxn];
	int ret=1;vis[P[1]]=true;
	for(int i=2;i<=n;i++)
	{
		bool flg=true;
		for(int j=1;j<i;j++)
			if(vis[P[j]]&&!E[P[i]][P[j]])
				{flg=false;break;}
		ret+=flg;vis[P[i]]=flg;
	}
	if(ret>ans) ans=ret;
	return ret;
}
inline void SA(double T)
{
	random_shuffle(P+1,P+1+n);
	int cur=Calc();
	while(T>1e-3)
	{
		int a=rand()%n+1,b=rand()%n+1;
		while(a==b){a=rand()%n+1;b=rand()%n+1;}
		swap(P[a],P[b]);
		int ret=Calc();
		if(ret>cur) cur=ret;
		else if(exp((ret-cur)/T)<(double)rand()/RAND_MAX) swap(P[a],P[b]);
		else cur=ret;
		T*=delta;
	}
}
int main()
{
	srand(20050413);
	scanf("%d",&n);
	int a,b;
	while(scanf("%d%d",&a,&b)==2) E[a][b]=E[b][a]=true;
	for(int i=1;i<=n;i++) P[i]=i;
	for(int i=1;i<=100;i++) SA((20020222+20050413+20040302)*6.4);
	printf("%d\n",ans);
	return 0;
}